COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00004 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a20.tex[154,phy] \today\hfill}

\parskip5pt
\parindent0pt
\bigskip
\disleft 38pt::
{\bf Exercise:} Show the following are equivalent for deterministic finite
automata:

%\display 60pt: (1): For every string $x\in\Sigma↑{\ast}$, there is a
%string $y\in\Sigma↑{\ast}$, for which, for every~$q$,, $\delta(q,xy)=q$.

\display 60pt: (1): $(\forall x\in\Sigma↑{\ast})(\exists y\in\Sigma↑{\ast})
(\forall q\in Q)(q\,\delta↓{xy}\,q)$. That is, every string can be extended
on the right to make a string whose transition function is the identity
function.

\display 60pt: (2): For every letter $a\in\Sigma$, column~$a$ of the
transition function table contains every state.

\display 60pt: (3): For every letter $a\in\Sigma$, column~$a$ does not
contain any state twice.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 16, 1984

\bye